package LinkedList;

public class _147_InsertionSortList {
    //选择排序，非插入
    public ListNode insertionSortList0(ListNode head) {
        ListNode p  = head;
        while(p!=null){
            int tempMin = p.val;
            ListNode pNext = p.next;
            while(pNext!=null){
                if(pNext.val<tempMin){
                    tempMin = pNext.val;
                }
                pNext = pNext.next;
            }
            ListNode pSort = p.next;
            while(pSort!=null){
                if(pSort.val==tempMin){
                    int temp = p.val;
                    p.val = tempMin;
                    pSort.val = temp;
                    break;
                }
                pSort = pSort.next;
            }
            p = p.next;
        }
        return head;
    }
    //插入排序，利用链表的改变结构方便的特性，从首部加入,参考
    public ListNode insertionSortList(ListNode head) {
        ListNode begin = new ListNode(Integer.MIN_VALUE);
        while (head != null) {
            ListNode temp = head.next;
            ListNode p = begin;
            while (p.next != null && p.next.val <= head.val) {
                p = p.next;
            }
            if (p.next == null) {
                p.next = head;
                head.next = null;
            } else if (p.next.val > head.val) {
                    ListNode y = p.next;
                    p.next = head;
                    head.next = y;
                }
                head = temp;
            }
            return begin.next;
    }
}
